package com.tang.algorithm.swordFingerOffer;

/**
 * @author tlm
 * @version 1.0
 * @date 2020/5/3 19:42
 * 链表中倒数第k个节点
 * <p>
 * https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
 */
public class TheKThLastNodeInTheLinkedList {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        ListNode temp = getKthFromEnd(listNode1, 2);
        System.out.println(temp.val);

    }

    //    /**
//     * 暴力解法
//     * @param head
//     * @param k
//     * @return
//     */
//    public static ListNode getKthFromEnd(ListNode head, int k) {
//        ListNode temp = head;
//        int size = 1;
//        while (temp.next != null) {
//            size++;
//            temp = temp.next;
//        }
//        temp = head;
//        int target = size - k;
//        for (int i = 1; i <= target; i++) {
//            temp = temp.next;
//        }
//        return temp;
//    }

    /**
     * 双指针解法
     * @param head
     * @param k
     * @return
     */
    public static ListNode getKthFromEnd(ListNode head, int k) {
        ListNode latter = head;
        ListNode former = head;
        while (k>0){
            former=former.next;
            k--;
        }
        while (former!=null){
            latter=latter.next;
            former=former.next;
        }
        return latter;
    }
}
